package cn.leonis.leetcode;

import java.util.HashMap;
import java.util.Map;

/**
 * @Author Tobi
 * @Date 2021-07-16 下午1:45
 * 找出字符串中第一个出现的唯一字符
 */
public class FindFirstUniqueCharacterInStringSolution {

    public static void main(String[] args) {
        String s = "aabcb";
        FindFirstUniqueCharacterInStringSolution solution = new FindFirstUniqueCharacterInStringSolution();
        System.out.println(solution.firstUniqChar1(s));
    }

    /**
     * 遍历两次，第一次将所有的字符都记录下来，第二次遍历取出其出现次数
     * @param s
     * @return
     */
    public int firstUniqChar(String s) {
        Map<Character, Integer> map = new HashMap<>();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            map.put(c, map.getOrDefault(c, 0) + 1);
        }

        for (int i = 0; i < s.length(); i++) {
            if (map.get(s.charAt(i)) == 1) {
                return i;
            }
        }

        return -1;
    }


    /**
     * 优化上述前面的解法，将出现多次的改为-1，如果所有都是-1,那就是-1
     * @param s
     * @return
     */
    public int firstUniqChar1(String s) {
        Map<Character, Integer> position = new HashMap<>();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (position.containsKey(c)) {
                position.put(c, -1);
            } else {
                position.put(c, i);
            }
        }

        // 由于直接遍历Map，其出现的顺序不一定是跟字符串出现顺序一致，因此需要比较确定第一个出现，只是遍历Map的话，最多也就遍历字母的次数
        int first = s.length();

        for (Map.Entry<Character, Integer> entry : position.entrySet()) {
            int pos = entry.getValue();
            if (pos != -1 && pos < first) {
                first = pos;
            }
        }

        if (first == s.length()) {
            first = -1;
        }

        return first;

    }
}
